package Oj;

public class ComminuteList {


     static class ListNode {
    int val;
    ListNode next;


     ListNode(int x) {
    this.val = x;
    }
  }
 public  ListNode head;
     /*
     * 头插法*/
     public void addFirst(int date){

         ListNode listNode=new ListNode(date);

         if(head==null) {
             this.head = listNode;
            return;
         }
                 listNode.next=this.head;
                this.head=listNode;
     }

/*
https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
CM11 链表分割
* 描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
* */
    public ListNode partition(ListNode Head, int x) {
        if(Head==null){//判断数组为空
            return null;
        }
        // write code here
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=Head;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=cur;
                }
            }else{//>=x
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;
                }

            }
            cur=cur.next;

        }
        if(bs==null){//判断小于x的没有数据，直接返回as大于x的链表
            return as;
        }

        if(as!=null){
            ae.next=null;//手动把链表的最后一个节点为空，防止cur最后一个节点小于x，导致ae最后一个节点不为空
        }
        be.next=as;//连接两个链表
        return bs;

    }

/*
* . 相交链表oJ链接
* https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
*
* intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

*/

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA != null && headB != null) {
            ListNode cur1 = headA;
            ListNode cur2 = headB;

            int num1 = 0;
            int num2 = 0;
            int tmp = 0;

            while (cur1 != null) {
                cur1 = cur1.next;
                num1++;
            }
            while (cur2 != null) {
                cur2 = cur2.next;
                num2++;
            }/*  */
            if (num1 <= num2) {
                cur1 = headB;
                cur2 = headA;
                tmp = num2 - num1;
            }else{
                cur1 = headA;
                cur2 = headB;
                tmp = num1 - num2;
            }


            while (tmp != 0) {
                cur1 = cur1.next;
                --tmp;
            }

            while (cur1 != null && cur2 != null) {
                if (cur1 != cur2) {
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                } else {
                    return cur1;
                }
            }

        }

        return null;
    }
}
